use crate::libc;

pub struct List<T> {
    pub head: *mut Node<T>,
    pub size: usize,
}

pub struct Node<T> {
    pub value: T,
    pub prev: *mut Node<T>,
    pub next: *mut Node<T>,
}

//=====================================================================//
//                        Create and Destory                           //
//=====================================================================//

pub unsafe fn create<T>() -> *mut List<T> {
    let lst = libc::malloc_value::<List<T>>();
    
    /*
        [head] <--prev-- [head] --next--> [head]
    */
    (*lst).head = libc::malloc_value::<Node<T>>();
    (*(*lst).head).next = (*lst).head;
    (*(*lst).head).prev = (*lst).head;
    (*lst).size = 0;
    
    lst
}

pub unsafe fn destory<T>(lst: *mut List<T>) {
    for_each(lst, destory_ndoe::<T>);
    destory_ndoe((*lst).head);
    libc::free_value(lst);
} 

unsafe fn new_node<T>(value: T) -> *mut Node<T> {
    let node = libc::malloc_value::<Node<T>>();
    (*node).value = value;
    (*node).next = core::ptr::null_mut();
    node
}

unsafe fn destory_ndoe<T>(node: *mut Node<T>) {
    libc::free_value(node);
}

//=====================================================================//
//                              Push                                   //
//=====================================================================//

pub unsafe fn push_back<T>(lst: *mut List<T>, value: T) {
    let head_node = (*lst).head;
    let last_node = (*head_node).prev;
    push_after(lst, last_node, value);
}

pub unsafe fn push_front<T>(lst: *mut List<T>, value: T) {
    let head_node = (*lst).head;
    push_after(lst, head_node, value);
}

pub unsafe fn push_at<T>(lst: *mut List<T>, value: T, index: usize) -> bool {
    if size(lst) < index {
        false
    } else {
        let head_node = (*lst).head;
        let mut prev_node = head_node;
        for _ in 0..index {
            prev_node = (*prev_node).next;
        }

        push_after(lst, prev_node, value);

        true
    }   
}

unsafe fn push_after<T>(lst: *mut List<T>, prev_node: *mut Node<T>, value: T) {
    let new_node = new_node(value);
    let next_node = (*prev_node).next;
        /*
            [prev] -> [next]
                    |
                    V
            [prev] -> [new] -> [next]
        */
    (*new_node).prev = prev_node;
    (*new_node).next = next_node;
    (*prev_node).next = new_node;
    (*next_node).prev = new_node;

    (*lst).size += 1;
}

//=====================================================================//
//                              Remove                                 //
//=====================================================================//

pub unsafe fn remove_back<T>(lst: *mut List<T>) -> Option<T> {
    if size(lst) == 0 {
        None
    } else {
        let head = (*lst).head;
        let last_node = (*head).prev;
        Some(remove_node(lst, last_node))
    }
}

pub unsafe fn remove_front<T>(lst: *mut List<T>) -> Option<T> {
    if size(lst) == 0 {
        None
    } else {
        let head = (*lst).head;
        let node = (*head).next;
        Some(remove_node(lst, node))
    }
}

pub unsafe fn remove_at<T>(lst: *mut List<T>, index: usize) -> Option<T> {
    if size(lst) < index {
        None
    } else {
        let node = nth_node(lst, index)?;
        Some(remove_node(lst, node))
    } 
}

unsafe fn remove_node<T>(lst: *mut List<T>, remove_node: *mut Node<T>) -> T {
    let prev_node = (*remove_node).prev;
    let next_node = (*remove_node).next;

    /*
        [prev] -> [remove] -> [next]
                |
                V
        [prev] -> [next]
    */

    (*prev_node).next = next_node;
    (*next_node).prev = prev_node;

    let mut value: T = core::mem::zeroed();
    libc::memcpy_value(&mut value, &mut ((*remove_node).value));
    destory_ndoe(remove_node);

    (*lst).size -= 1;

    value
}

//=====================================================================//
//                               Util                                  //
//=====================================================================//

pub unsafe fn get<T>(lst: *mut List<T>, index: usize) -> Option<*mut T> {
    nth_node(lst, index).map(|node| -> *mut T {&mut (*node).value})
}

pub unsafe fn container<T: PartialEq>(lst: *mut List<T>, value: &T) -> bool {
    let head = (*lst).head;
    let mut node = (*head).next;
    while node != head {
        let cur = node;
        node = (*node).next;
        if (*cur).value == *value {
            return true;
        }
    }

    false
}

pub unsafe fn size<T>(lst: *mut List<T>) -> usize {
    (*lst).size
}

pub unsafe fn is_empty<T>(lst: *mut List<T>) -> bool {
    size(lst) == 0
}

pub unsafe fn clear<T>(lst: *mut List<T>) {
    for_each(lst, destory_ndoe::<T>);
    let head = (*lst).head;
    (*head).next = head;
    (*head).prev = head;
    (*lst).size = 0;
}

pub unsafe fn nth_node<T>(lst: *mut List<T>, index: usize) -> Option<*mut Node<T>> {
    if size(lst) <= index {
        None
    } else {
        let head_node = (*lst).head;
        let mut node = (*head_node).next;
        for _ in 0..index {
            node = (*node).next;
        }

        Some(node)
    }
}

pub unsafe fn for_each<T>(lst: *mut List<T>, f: unsafe fn (*mut Node<T>)) {
    let head = (*lst).head;
    let mut node = (*head).next;
    while node != head {
        let cur = node;
        node = (*node).next;
        f(cur);
    }
}

#[allow(unused)]
#[cfg(test)]
mod test {
    #[test]
     fn test_push() {
        unsafe {
            let lst = super::create::<i32>();
            super::push_back(lst, 12);
            super::push_back(lst, 12);
            super::push_front(lst, 12);
            super::push_front(lst, 12);
            super::push_at(lst, 1, 0);
            assert_eq!(5, super::size(lst));
            super::destory(lst);
        }
    }

    #[test]
    fn test_remove() {
        unsafe {
            let lst = super::create::<i32>();
            super::push_back(lst, 1);
            super::push_back(lst, 2);
            super::push_back(lst, 3);
            super::push_back(lst, 4);
            super::push_back(lst, 5);

            assert_eq!(Some(5), super::remove_back(lst));
            assert_eq!(Some(1), super::remove_front(lst));
            assert_eq!(Some(3), super::remove_at(lst, 1));

            super::destory(lst);
        }
    }

    #[test]
    fn test_else() {
        unsafe {
            let lst = super::create::<i32>();
            super::push_back(lst, 1);
            super::push_back(lst, 2);
            super::push_back(lst, 3);
            super::push_back(lst, 4);
            super::push_back(lst, 5);

            assert_eq!(super::container(lst, &1), true);
            assert_eq!(super::container(lst, &10), false);

            super::remove_at(lst, 3);
            assert_eq!(super::container(lst, &4), false);

            assert_eq!(super::size(lst), 4);
            super::clear(lst);
            assert_eq!(super::size(lst), 0);

            super::destory(lst);
        }
    }
}